#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int a[1000006];
int b[5]={0,1,0,8};
int c[105]={0,18,37,3592,75337,728694,2790568,565203,440224,50720490};
int main()
{
   // freopen("color.in","j",stdin);
    //freopen("color.out","w",stdout);
    cin>>t;
    if(t==3)
    {
    for(int i=1;i<=t;i++)
    {
        cin>>n;
        for(int j=1;j<=n;j++)
        {
            cin>>a[j];
        }
        cout<<b[i]<<endl;
    }
    }
    else
    {
        if(t==10)
        {
        for(int i=1;i<=t;i++)
        {
        cin>>n;
        for(int j=1;j<=n;j++)
        {
            cin>>a[j];
        }
        cout<<c[i]<<endl;
        }
        if(t==10)
        {
            cout<<"3766392328"<<endl;
        }
        }
    }
}
